package datastructure.array;

/**
 * The array is sorted and sorted.
 * e.g. 3 4 5 6 7 1 2
 * Find the minimum (assume ascending order and no duplicate)
 * 
 * @author Lei
 */
public class FindMinimumInRotatedSortedArray {
  public static int findMinimumInRotatedSortedArray_Recursive(int[] array,
      int start,
      int end) {

    if (array[start] < array[end]) {
      return array[start];
    }

    int middle = (start + end) / 2;
    if (array[middle] > array[middle + 1]) {
      return array[middle + 1];
    } else if (array[start] < array[middle]) {
      return findMinimumInRotatedSortedArray_Recursive(array, middle, end);
    } else {
      return findMinimumInRotatedSortedArray_Recursive(array, start, middle);
    }
  }

  public static int findMinimumInRotatedSortedArray_Iterative(int[] array,
      int start, int end) {
    while (array[start] > array[end]) {
      int middle = (start + end) / 2;
      if (array[middle] > array[end]) {
        start = middle + 1;
      } else {
        end = middle;
      }
    }

    return array[start];

  }

  public static void main(String[] args) {
    int[] array1 = {3,
      4,
      5,
      6,
      7,
      1,
      2};
//    int[] array1 = {1,
//      2,
//      3,
//      4,
//      5,
//      6,
//      7};
    int min = findMinimumInRotatedSortedArray_Iterative(array1, 0, array1.length - 1);

    System.out.println(min);
  }
}
